package com.rising.face.ali.bishi.treeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: rising
 * @Description:
 * 给定一个二叉树 :
 *        1
 *     / \
 *    2   4
 *   / \
 *  2   3
 * 目标值= 5时返回结果：
 * 1 2 2
 * 1 4
 * @Date: create in 2021/2/28 20:06
 */
public class FindTreePath {

    ArrayList<ArrayList<Integer>> pathList = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> path = new ArrayList<Integer>();

    public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
        if(root == null)
            return  pathList;
        path.add(root.val);
        if (root.left == null && root.right == null && target == root.val) {
            pathList.add(new ArrayList<Integer>(path));
        }
        if(root.val <= target && root.left != null) {
            findPath(root.left,target-root.val);
        }
        if(root.val <= target && root.right != null) {
            findPath(root.right,target-root.val);
        }
        path.remove(path.size()-1);//回退到父节点
        return pathList;
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode2_2 = new TreeNode(2);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode4;
        treeNode2.left = treeNode2_2;
        treeNode2.right = treeNode3;

        FindTreePath findTreePath = new FindTreePath();
        ArrayList<ArrayList<Integer>> path = findTreePath.findPath(treeNode1, 5);
        System.out.println(path);
    }
}
